树链剖分

树链剖分主要用来解决：

$$\boxed{\text{树上的路径修改 / 查询问题}}$$

尤其是当你需要动态维护树上信息时，它非常有用。

算法步骤

1. 求树的重儿子和重边。

定义 重节点 表示子节点中子树最大的那一个，如果有多个子树最大的则任取一个。

定义 轻节点 为剩余的子节点。

父节点与重节点相连的边称为 重边，其余的边称为 轻边。

相连的重边称为 重链。

提示

$n$ 个节点的树，重边最少可以只有一条，此时节点 $2\sim n$ 均直接与节点 $1$ 相连。

重边最多可以有 $n - 1$ 条，即每条边都是重边，此时树退化为一条链。

每经过一条轻边，就会新开一条重链。 重链数等于轻边数 + 1。因此，当轻边最多的时候，重链最多。当 $2 \sim n$ 直接和 $1$ 号节点相连，此时轻边数量最多，为 $n - 2$，所以重链数为 $n - 1$。

上图给出了一棵树的重链剖分。圈中的数字表示子树的大小。

参考代码

void dfs1(int x, int f) {
    fa[x] = f; // x 的父节点为 f
    dep[x] = dep[f] + 1; // 深度
    siz[x] = 1; // 子树大小

    for (int y : e[x]) {
        if (y == f) continue;

        dfs1(y, x);

        siz[x] += siz[y];

        if (!son[x] || siz[y] > siz[son[x]])
            son[x] = y;
    }
}

2. 求出树的重链

按照重节点优先的原则对树进行 dfs。

这样可以划分出重链，并且重链上的节点将具有连续的 dfs 序，同时记录每条重链的链顶。

参考代码

void dfs2(int x, int t) {
    top[x] = t; // 链顶
    dfn[x] = ++cnt; // dfs 序
    rnk[cnt] = x;

    if (son[x]) dfs2(son[x], t);

    for (int y : e[x]) {
        if (y == fa[x] || y == son[x]) continue;
        dfs2(y, y);
    }
}

性质

1. 树上每个结点都属于且仅属于一条重链．
2. 重链开头的结点一定不是重子结点（因为重链开头的结点要么是根，要么是其父亲结点的轻子结点）。
3. 所有的重链将整棵树完全剖分．
4. 树的 DFS 序上，重链内的 DFS 序是连续的．按 DFN 排序后的序列即为剖分后的链． 比如上面的图中，我们用 DFN 值代表节点，那么，整棵树就划分为如下几条链。

1,2,3,4,5,6 / 7 / 8 / 9,10 / 11,12,13,14 / 15 / 16,17,18 / 19

5. 由轻重边的定义，从节点走向一条轻边，对应的子树大小减半。对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 $O(\log n)$ 次轻边。因为从祖先节点走向子孙节点，总是 重链-轻边-重链-轻边-重链 的步骤，因此，树上的每条路径都可以被拆分成不超过 $O(\log n)$ 条重链。

应用

求 LCA

设两点为 $u$ 和 $v$。

若 $u$ 和 $v$ 位于同一条重链上，那么，$u$、$v$ 中更浅的那个就是 lca。

若 $u$ 和 $v$ 位于不同的重链上，则我们比较他们链顶的深度，若 $top[u]$ 的深度更大，则可以直接跳过 $u \sim top[u]$ 这段，继续寻找 $fa[top[u]]$ 和 $v$ 的 lca。

int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);    
    u = fa[top[u]];
  }
  return dep[u] > dep[v] ? v : u;
}

路径查询、修改，子树查询、修改、换根

提示

给定一棵 $n$ 个节点的树，初始时该树的根为 $1$ 号节点，每个节点有一个给定的权值。下面依次进行 $m$ 个操作，操作分为如下五种类型：

• 换根：将一个指定的节点设置为树的新根。

• 修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。

• 修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。

• 询问路径：询问某条路径上节点的权值和。

• 询问子树：询问某个子树内节点的权值和。

以 $1$ 为根，进行树链剖分，求出所需信息。

路径查询和修改

按照求 LCA 的步骤，找到端点走向 LCA 的过程中，经过的每一段重链进行查询和修改即可。注意到换根以后，两点之间的路径不会改变。故换根不影响路径查询和修改。

子树查询和修改

在换根之前，子树 $x$ 对应 dfs 序 $[\text{dfn[x]}, \text{dfn}[x] + \text{sz}[x] - 1]$。

考虑换根对子树的影响。

设新的根为 root，查询的子树为 $u$。

1. 若子树 $u$ 和 root 没有父子关系或者 $u$ 是 root 的子孙节点，或等于 root。此时将 root 设为新的根不影响子树 $u$。

情况1

情况2

2. 若 $u$ 是 root 的父节点。

注意到将 root 设为新的根以后，设 $c$ 为 $u$ 的儿子节点中，指向 $root$ 的部分，子树 $u$ 将会变成整棵树，去掉子树 $c$ 的部分。

因此，根变成 root 以后，找到子树 $c$，子树 $c$ 对应的区间为 $[\text{dfn}[c], \text{dfn}[c] + \text{sz}[c] - 1]$。我们只需区间 $[1, n]$ 去掉该区间然后进行查询、修改即可。